package 链表;

public class BM15_删除有序链表中重复的元素I {

	public static void main(String[] args) {
		ListNode node1 = new ListNode(1);
		ListNode node2 = new ListNode(1);
		ListNode node3 = new ListNode(1);
		node1.next = node2;
		node2.next = node3;
		BM15_删除有序链表中重复的元素I test = new BM15_删除有序链表中重复的元素I();
		System.out.println(test.deleteDuplicates(node1));
	}

	// 遍历删除（推荐使用）
	public ListNode deleteDuplicates01 (ListNode head) {
		if(head == null) return head;
		ListNode curr = head;
		while(curr != null && curr.next != null) {
			if(curr.val == curr.next.val) {
				curr.next = curr.next.next;
			}else {
				curr = curr.next;
			}
		}
		return head;
    }
	
	// 新建链表
	public ListNode deleteDuplicates02 (ListNode head) {
		if(head == null) return head;
		ListNode res = new ListNode(head.val);// 新建节点
		ListNode poc = res;    // 遍历节点
		while(head != null) {
			// 遍历时找到一个非重复的节点则加入新链表后面
			if(head.val != poc.val) {
				poc.next = new ListNode(head.val);
				poc = poc.next;
			}
			head = head.next;// 遍历原链表
		}
		return res;
	}
	
	// 递归
	public ListNode deleteDuplicates (ListNode head) {
		 //节点不存在或者只有一个节点时，递归结束
		 if (head == null || head.next == null) return head;
		 //递归体，每次递归从下一个节点开始
		 head.next = deleteDuplicates(head.next);
		 //比较当前元素和下一个元素的值是否相等，相等则直接删除当前节点
		 if(head.val == head.next.val)
			 //head指针指向下一个节点，表明当前节点丢失，已经不再属于这个链表
			 head = head.next;
		 return head;//返回本次递归的结果
	}
}
